Bregman divergence

 ( Geometric Algorithms ) 

In mathematics, specifically statistics and information geometry, a Bregman divergence or Bregman distance is a measure of difference between two points, defined in terms of a strictly convex function; they form an important class of divergences. When the points are interpreted as probability distributions – notably as either values of the parameter of a parametric model or as a data set of observed values – the resulting distance is a statistical distance. The most basic Bregman divergence is the squared Euclidean distance.

Bregman divergences are similar to metrics, but satisfy neither the triangle inequality (ever) nor symmetry (in general). However, they satisfy a generalization of the Pythagorean theorem, and in information geometry the corresponding statistical manifold is interpreted as a (dually) flat manifold. This allows many techniques of optimization theory to be generalized to Bregman divergences, geometrically as generalizations of least squares.

Bregman divergences are named after Russian mathematician Lev M. Bregman, who introduced the concept in 1967.

---

Definition Let $F\backslash colon\; \backslash Omega\; \backslash to\; \backslash mathbb\{R\}$ be a continuously-differentiable, strictly convex function defined on a convex set $\backslash Omega$.

The Bregman distance associated with F for points $p,\; q\; \backslash in\; \backslash Omega$ is the difference between the value of F at point p and the value of the first-order Taylor expansion of F around point q evaluated at point p:

$D\_F(p,\; q)\; =\; F(p)-F(q)-\backslash langle\; \backslash nabla\; F(q),\; p-q\backslash rangle.$

---

Properties

• Non-negativity: $D\_F(p,\; q)\; \backslash ge\; 0$ for all $p$, $q$. This is a consequence of the convexity of $F$.
• Positivity: When $F$ is strictly convex, $D\_F(p,\; q)\; =\; 0$ iff $p=q$.
• Uniqueness up to affine difference: $D\_F\; =\; D\_G$ iff $F-G$ is an affine function.
• Convexity: $D\_F(p,\; q)$ is convex in its first argument, but not necessarily in the second argument. If F is strictly convex, then $D\_F(p,\; q)$ is strictly convex in its first argument.
• For example, Take f(x) = |x|, smooth it at 0, then take $y\; =\; 1,\; x\_1\; =\; 0.1,\; x\_2\; =\; -0.9,\; x\_3\; =\; 0.9x\_1\; +\; 0.1x\_2$, then $D\_f(y,\; x\_3)\; \backslash approx\; 1\; >\; 0.9\; D\_f(y,\; x\_1)\; +\; 0.1\; D\_f(y,\; x\_2)\; \backslash approx\; 0.2$.
• Linearity: If we think of the Bregman distance as an operator on the function F, then it is linear with respect to non-negative coefficients. In other words, for $F\_1,\; F\_2$ strictly convex and differentiable, and $\backslash lambda\; \backslash ge\; 0$,

:$D\_\{F\_1\; +\; \backslash lambda\; F\_2\}(p,\; q)\; =\; D\_\{F\_1\}(p,\; q)\; +\; \backslash lambda\; D\_\{F\_2\}(p,\; q)$

• Duality: If F is strictly convex, then the function F has a convex conjugate $F^*$ which is also strictly convex and continuously differentiable on some convex set $\backslash Omega^*$. The Bregman distance defined with respect to $F^*$ is dual to $D\_F(p,\; q)$ as

:$D\_\{F^*\}(p^*,\; q^*)\; =\; D\_F(q,\; p)$

Here, $p^*\; =\; \backslash nabla\; F(p)$ and $q^*\; =\; \backslash nabla\; F(q)$ are the dual points corresponding to p and q.

Moreover, using the same notations :

:$D\_\{F\}(p,\; q)\; =\; F(p)\; +\; F^*(q^*)\; -\; \backslash langle\; p,\; q^*\; \backslash rangle$

• Integral form: by the integral remainder form of Taylor's Theorem, a Bregman divergence can be written as the integral of the Hessian of $F$ along the line segment between the Bregman divergence's arguments.

• Mean as minimizer: A key result about Bregman divergences is that, given a random vector, the mean vector minimizes the expected Bregman divergence from the random vector. This result generalizes the textbook result that the mean of a set minimizes total squared error to elements in the set. This result was proved for the vector case by (Banerjee et al. 2005), and extended to the case of functions/distributions by (Frigyik et al. 2008). This result is important because it further justifies using a mean as a representative of a random set, particularly in Bayesian estimation.
• Bregman balls are bounded, and compact if X is closed: Define Bregman ball centered at x with radius r by $B\_f(x,\; r):=\; \backslash left\backslash \{y\backslash in\; X:\; D\_f(y,\; x)\backslash leq\; r\backslash right\backslash \}$. When $X\backslash subset\; \backslash R^n$ is finite dimensional, $\backslash forall\; x\backslash in\; X$, if $x$ is in the relative interior of $X$, or if $X$ is locally closed at $x$ (that is, there exists a closed ball $B(x,\; r)$ centered at $x$, such that $B(x,r)\; \backslash cap\; X$ is closed), then $B\_f(x,\; r)$ is bounded for all $r$ . If $X$ is closed, then $B\_f(x,\; r)$ is compact for all $r$.
• Law of cosines:

For any $p,q,z$

:$D\_F(p,\; q)\; =\; D\_F(p,\; z)\; +\; D\_F(z,\; q)\; -\; (p\; -\; z)^T(\backslash nabla\; F(q)\; -\; \backslash nabla\; F(z))$

• Parallelogram law: for any $\backslash theta,\; \backslash theta\_1,\; \backslash theta\_2$,

$B\_\{F\}\backslash left(\backslash theta\_\{1\}:\; \backslash theta\backslash right)+B\_\{F\}\backslash left(\backslash theta\_\{2\}:\; \backslash theta\backslash right)=B\_\{F\}\backslash left(\backslash theta\_\{1\}:\; \backslash frac\{\backslash theta\_\{1\}+\backslash theta\_\{2\}\}\{2\}\backslash right)+B\_\{F\}\backslash left(\backslash theta\_\{2\}:\; \backslash frac\{\backslash theta\_\{1\}+\backslash theta\_\{2\}\}\{2\}\backslash right)+2\; B\_\{F\}\backslash left(\backslash frac\{\backslash theta\_\{1\}+\backslash theta\_\{2\}\}\{2\}:\; \backslash theta\backslash right)$

• Bregman projection: For any $W\backslash subset\; \backslash Omega$, define the "Bregman projection" of $q$ onto $W$:

$P\_W(q)\; =\; \backslash text\{argmin\}\_\{\backslash omega\backslash in\; W\}\; D\_F(\backslash omega,\; q)$. Then

• if $W$ is convex, then the projection is unique if it exists;
• if $W$ is nonempty, closed, and convex and $\backslash Omega\backslash subset\; \backslash R^n$ is finite dimensional, then the projection exists and is unique.
• Generalized Pythagorean Theorem:

For any $v\backslash in\; \backslash Omega,\; a\backslash in\; W$,

$D\_F(a,\; v)\; \backslash ge\; D\_F(a,\; P\_W(v))\; +\; D\_F(P\_W(v),\; v).$

This is an equality if $P\_W(v)$ is in the relative interior of $W$.

In particular, this always happens when $W$ is an affine set.

• Lack of triangle inequality: Since the Bregman divergence is essentially a generalization of squared Euclidean distance, there is no triangle inequality. Indeed, $D\_F(z,\; x)\; -\; D\_F(z,\; y)\; -\; D\_F(y,\; x)\; =\; \backslash langle\backslash nabla\; f(y)\; -\; \backslash nabla\; f(x),\; z-y\backslash rangle$, which may be positive or negative.

---

Proofs

• Non-negativity and positivity: use Jensen's inequality.
• Uniqueness up to affine difference: Fix some $x\backslash in\; \backslash Omega$, then for any other $y\backslash in\; \backslash Omega$, we have by definition$F(y)\; -\; G(y)\; =\; F(x)\; -\; G(x)\; +\; \backslash langle\backslash nabla\; F(x)\; -\; \backslash nabla\; G(x)\; ,\; y-x\; \backslash rangle$.
• Convexity in the first argument: by definition, and use convexity of F. Same for strict convexity.
• Linearity in F, law of cosines, parallelogram law: by definition.
• Duality: See figure 1 of.
• Bregman balls are bounded, and compact if X is closed:

Fix $x\backslash in\; X$ . Take affine transform on $f$ , so that $\backslash nabla\; f(x)\; =\; 0$.

Take some $\backslash epsilon\; >\; 0$, such that $\backslash partial\; B(x,\; \backslash epsilon)\; \backslash subset\; X$. Then consider the "radial-directional" derivative of $f$ on the Euclidean sphere $\backslash partial\; B(x,\; \backslash epsilon)$.

$\backslash langle\backslash nabla\; f(y),\; (y-x)\backslash rangle$ for all $y\backslash in\; \backslash partial\; B(x,\; \backslash epsilon)$.

Since $\backslash partial\; B(x,\; \backslash epsilon)\backslash subset\; \backslash R^n$ is compact, it achieves minimal value $\backslash delta$ at some $y\_0\backslash in\; \backslash partial\; B(x,\; \backslash epsilon)$.

Since $f$ is strictly convex, $\backslash delta\; >\; 0$. Then $B\_f(x,\; r)\backslash subset\; B(x,\; r/\backslash delta)\backslash cap\; X$.

Since $D\_f(y,\; x)$ is $C^1$ in $y$, $D\_f$ is continuous in $y$, thus $B\_f(x,\; r)$ is closed if $X$ is.

• Projection $P\_W$ is well-defined when $W$ is closed and convex.

Fix $v\backslash in\; X$. Take some $w\backslash in\; W$ , then let $r\; :=\; D\_f(w,\; v)$. Then draw the Bregman ball $B\_f(v,\; r)\backslash cap\; W$. It is closed and bounded, thus compact. Since $D\_f(\backslash cdot,\; v)$ is continuous and strictly convex on it, and bounded below by $0$, it achieves a unique minimum on it.

• Pythagorean inequality.

By cosine law, $D\_f(w,\; v)\; -\; D\_f(w,\; P\_W(v))\; -\; D\_f(P\_W(v),\; v)\; =\; \backslash langle\; \backslash nabla\_y\; D\_f(y,\; v)|\_\{y\; =\; P\_W(v)\}\; ,\; w\; -\; P\_W(v)\backslash rangle$, which must be $\backslash geq\; 0$, since $P\_W(v)$ minimizes $D\_f(\backslash cdot,\; v)$ in $W$, and $W$ is convex.

• Pythagorean equality when $P\_W(v)$ is in the relative interior of $X$.

If $\backslash langle\; \backslash nabla\_y\; D\_f(y,\; v)|\_\{y\; =\; P\_W(v)\},\; w\; -\; P\_W(v)\backslash rangle\; >\; 0$, then since $w$ is in the relative interior, we can move from $P\_W(v)$ in the direction opposite of $w$, to decrease $D\_f(y,\; v)$ , contradiction.

Thus $\backslash langle\; \backslash nabla\_y\; D\_f(y,\; v)|\_\{y\; =\; P\_W(v)\},\; w\; -\; P\_W(v)\backslash rangle\; =\; 0$.

---

Classification theorems

• The only symmetric Bregman divergences on $X\backslash subset\; \backslash R^n$ are squared generalized Euclidean distances (Mahalanobis distance), that is, $D\_f(y,\; x)\; =\; (y-x)^T\; A\; (y-x)$ for some positive definite $A$.

The following two characterizations are for divergences on $\backslash Gamma\_n$, the set of all probability measures on $\backslash \{1,\; 2,\; ...,\; n\backslash \}$, with $n\; \backslash geq\; 2$.

Define a divergence on $\backslash Gamma\_n$ as any function of type $D:\; \backslash Gamma\_n\; \backslash times\; \backslash Gamma\_n\; \backslash to\; 0,$, such that $D(x,\; x)\; =\; 0$ for all $x\backslash in\backslash Gamma\_n$, then:

• The only divergence on $\backslash Gamma\_n$ that is both a Bregman divergence and an f-divergence is the Kullback–Leibler divergence.
• If $n\; \backslash geq\; 3$, then any Bregman divergence on $\backslash Gamma\_n$ that satisfies the data processing inequality must be the Kullback–Leibler divergence. (In fact, a weaker assumption of "sufficiency" is enough.) Counterexamples exist when $n\; =\; 2$.

Given a Bregman divergence $D\_F$, its "opposite", defined by $D\_F^*(v,\; w)\; =\; D\_F(w,\; v)$, is generally not a Bregman divergence. For example, the Kullback-Leiber divergence is both a Bregman divergence and an f-divergence. Its reverse is also an f-divergence, but by the above characterization, the reverse KL divergence cannot be a Bregman divergence.

---

Examples

• The squared Mahalanobis distance $D\_F(x,y)=\backslash tfrac\{1\}\{2\}(x-y)^T\; Q\; (x-y)$ is generated by the convex quadratic form $F(x)\; =\; \backslash tfrac\{1\}\{2\}\; x^T\; Q\; x$.
• The canonical example of a Bregman distance is the squared Euclidean distance $D\_F(x,y)\; =\; \backslash |x\; -\; y\backslash |^2$. It results as the special case of the above, when $Q$ is the identity, i.e. for $F(x)\; =\; \backslash |x\backslash |^2$. As noted, affine differences, i.e. the lower orders added in $F$, are irrelevant to $D\_F$.
• The generalized Kullback–Leibler divergence

:$D\_F(p,\; q)\; =\; \backslash sum\_i\; p(i)\; \backslash log\; \backslash frac\{p(i)\}\{q(i)\}\; -\; \backslash sum\; p(i)\; +\; \backslash sum\; q(i)$

is generated by the negative entropy function

:$F(p)\; =\; \backslash sum\_i\; p(i)\backslash log\; p(i)$

When restricted to the simplex, the last two terms cancel, giving the usual Kullback–Leibler divergence for distributions.

• The Itakura–Saito distance,

:$D\_F(p,\; q)\; =\; \backslash sum\_i\; \backslash left(\backslash frac\; \{p(i)\}\{q(i)\}\; -\; \backslash log\; \backslash frac\{p(i)\}\{q(i)\}\; -\; 1\; \backslash right)$

is generated by the convex function

:$F(p)\; =\; -\; \backslash sum\_i\; \backslash log\; p(i)$

---

Generalizing projective duality A key tool in computational geometry is the idea of projective duality, which maps points to hyperplanes and vice versa, while preserving incidence and above-below relationships. There are numerous analytical forms of the projective dual: one common form maps the point $p\; =\; (p\_1,\; \backslash ldots\; p\_d)$ to the hyperplane $x\_\{d+1\}\; =\; \backslash sum\_1^d\; 2p\_i\; x\_i$. This mapping can be interpreted (identifying the hyperplane with its normal) as the convex conjugate mapping that takes the point p to its dual point $p^*\; =\; \backslash nabla\; F(p)$, where F defines the d-dimensional paraboloid $x\_\{d+1\}\; =\; \backslash sum\; x\_i^2$.

If we now replace the paraboloid by an arbitrary convex function, we obtain a different dual mapping that retains the incidence and above-below properties of the standard projective dual. This implies that natural dual concepts in computational geometry like and Delaunay triangulations retain their meaning in distance spaces defined by an arbitrary Bregman divergence. Thus, algorithms from "normal" geometry extend directly to these spaces (Boissonnat, Nielsen and Nock, 2010)

---

Generalization of Bregman divergences Bregman divergences can be interpreted as limit cases of skewed Jensen divergences (see Nielsen and Boltz, 2011). Jensen divergences can be generalized using comparative convexity, and limit cases of these skewed Jensen divergences generalizations yields generalized Bregman divergence (see Nielsen and Nock, 2017). The Bregman chord divergence

(2025). 9783030269791 ISBN 9783030269791

is obtained by taking a chord instead of a tangent line.

---

Bregman divergence on other objects Bregman divergences can also be defined between matrices, between functions, and between measures (distributions). Bregman divergences between matrices include the Stein's loss and von Neumann entropy. Bregman divergences between functions include total squared error, relative entropy, and squared bias; see the references by Frigyik et al. below for definitions and properties. Similarly Bregman divergences have also been defined over sets, through a submodular set function which is known as the discrete analog of a convex function. The submodular Bregman divergences subsume a number of discrete distance measures, like the Hamming distance, precision and recall, mutual information and some other set based distance measures (see Iyer & Bilmes, 2012 for more details and properties of the submodular Bregman.)

For a list of common matrix Bregman divergences, see Table 15.1 in."Matrix Information Geometry", R. Nock, B. Magdalou, E. Briys and F. Nielsen, pdf, from this book

---

Applications In machine learning, Bregman divergences are used to calculate the bi-tempered logistic loss, performing better than the softmax function with noisy datasets.Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren (2019). "Robust Bi-Tempered Logistic Loss Based on Bregman Divergences". Conference on Neural Information Processing Systems. pp. 14987-14996. pdf

Bregman divergence is used in the formulation of mirror descent, which includes optimization algorithms used in machine learning such as gradient descent and the hedge algorithm.

Post Comment